#include "assert.h"

#include <algorithm>
#include <iostream>

using namespace std;

#include "tasktree.h"
#include "thread_utils.h"


class Filters
{
private:

    std::list<Filter *> m_filters;

public:

    void addFilter(Filter *filter);

    bool filt(const pid_t &pid);

    void filt(const std::set<pid_t> &all_pid, std::set<pid_t> *pass);

};

void Filters::addFilter(Filter *filter)
{
    if (filter) {
        m_filters.push_back(filter);
    }
}

bool Filters::filt(const pid_t &pid)
{
    for (Filter * filter : m_filters) {
        if (filter) {
            if (!filter->filt(pid)) {
                return false;
            }
        }
    }

    return true;
}

void Filters::filt(const std::set<pid_t> &all_pid, std::set<pid_t> *pass)
{
    if (pass) {

        for (pid_t pid : all_pid) {
            if (filt(pid)) {
                pass->insert(pid);
            }
        }

    }

}

/*
 * 进程树逻辑类
 * 实现了进程树的逻辑方面的操作，不关心线程安全，
 * 线程安全由其外层的包装类来保证。
*/
class TaskTree_Logic
{
public:

    struct Node
    {
        const pid_t pid;

        int index;

        Node * parent = nullptr;

        std::vector<Node *> children;

        TaskInfo task_info;

        // 用于TaskTree深拷贝
        Node(pid_t pid, const TaskInfo &info):pid(pid), task_info(info) {}

        // 用于TaskTree的刷新操作
        Node(pid_t pid):pid(pid),task_info(pid){}
    };

    TaskTree_Logic() {}

    // 深拷贝, 所有Node均被新建独立副本
    // 监听器和过滤器为外部代码提供，所以只需要简单使用默认的拷贝操作,不需要深拷贝
    TaskTree_Logic(const TaskTree_Logic &other);

    ~TaskTree_Logic();

    void addFilter(Filter * filter);

    void flush();

    void sort(TIP prop, SortOrder order);

    // 如果模式变化则返回true，上层代码需要更新状态。
    // 如果模式没有变化则返回false，上层代码不需要更新状态
    bool setTreeMode(bool treeMode);

    bool isTreeMode() const;

    SortOrder getSortOrder() const;

    SortBy getSortBy() const;

    int getRootCount() const;

    pid_t getRootAt(int n) const;

    int getTaskCount() const;

    bool contains(pid_t pid) const;

    int getChildCount(pid_t ppid) const;

    pid_t getChildAt(pid_t ppid, int n) const;

    bool hasParent(pid_t pid) const;

    pid_t getParent(pid_t pid) const;

    int getIndex(pid_t pid) const;

    void getInserted(std::vector<Location> *vec) const;

    void getRemoved(std::vector<Location> *vec) const;

    bool info(pid_t pid, TaskInfo *info) const;

private:

    class SorterWrapper
    {
    private:
        typedef bool sorter_t(Node *, Node *);
        sorter_t *sorter;
        const SortOrder order;
    public:
        SorterWrapper(sorter_t *sorter, SortOrder order);
        bool operator() (Node *, Node *);

    };

    //----------------members-----------------------------------------

    bool m_tree_mode = false;

    SortOrder m_sort_order = SortOrder::ASC;

    SortBy m_sort_by = SortBy::PID;

    Filters m_filters;

    std::vector<Node *> m_roots;

    std::map<pid_t, Node *> m_all_tasks;

    std::vector<Location> m_inserted;
    std::vector<Location> m_removed;
    /* 把移动拆分为删除和插入，简化逻辑 */

    //----------------end members-------------------------------------

    SorterWrapper _get_sorter();

    void _sort_node_vec(std::vector<Node *> &vec);

    void _sort_node(Node *node);

    void _sort(SortBy sortBy, SortOrder order, bool force);

    Node * _get_node(pid_t pid) const;

    void _filt(const std::set<pid_t> &all_pid, std::set<pid_t> *filted);

    void _which(const std::set<pid_t> &all_pid, std::set<pid_t> *old_pid, std::set<pid_t> *new_pid, std::set<pid_t> *out_of_date) const;

    void _delete_child_nodes_for_treemode(Node * node);

    void _delete_task_for_treemode(pid_t pid);

    void _delete_task_not_treemode(pid_t pid);

    void _delete_out_of_date(const std::set<pid_t> &out_of_date);

    void _erase(vector<Node *> &vec, pid_t pid);

    void _insert(vector<Node *> &vec, Node *node);

    void _load_new(const std::set<pid_t> &new_pid);

    void _flush_old(const std::set<pid_t> &old_pid, std::set<pid_t> * const &out_of_date);

    void _move(Node *node, pid_t old_ppid, pid_t new_ppid);

    /* 重新构造表示进程间树形关系的相关成员， 更新进程间的关系 */
    void _rebuild_tree();

    /* 删除表示进程间树形关系的相关成员，只是删除结点间的关系，不删除结点 */
    void _clear_tree();

    /* 重新构造表示进程间树形关系的相关成员 */
    void _build_tree();

    /* 从系统载入信息，更新对象 */
    void _load_from_sys();

};

typedef TaskTree_Logic::Node Node;

static Node * deep_copy_node(map<pid_t, Node *> *found_task, const Node *src)
{
    assert(found_task);
    assert(src);

    pid_t pid = src->pid;
    Node * node = new Node(pid, src->task_info);
    node->index = src->index;

    (*found_task)[pid] = node;

    for (Node * p : src->children) {
        Node * child = deep_copy_node(found_task, p);
        child->parent = node;
        node->children.push_back(child);
    }

    return node;
}

TaskTree_Logic::TaskTree_Logic(const TaskTree_Logic &other)
{
    this->m_tree_mode = other.m_tree_mode;
    this->m_sort_order = other.m_sort_order;
    this->m_sort_by = other.m_sort_by;
    this->m_filters = other.m_filters;

    for (Node * p : other.m_roots) {
        Node * a_root_node = deep_copy_node(&(this->m_all_tasks), p);
        a_root_node->parent = nullptr;
        m_roots.push_back(a_root_node);
    }
}

static inline bool set_contains(const set<pid_t> &set, pid_t pid)
{
    return set.find(pid) != set.end();
}

static inline bool map_contains(const map<pid_t, pid_t> &map, pid_t pid)
{
    return map.find(pid) != map.end();
}

static inline bool map_contains(const map<pid_t, Node *> &map, pid_t pid)
{
    return map.find(pid) != map.end();
}

Node * TaskTree_Logic::_get_node(pid_t pid) const
{
    map<pid_t, Node *>::const_iterator iter = m_all_tasks.find(pid);
    if (iter == m_all_tasks.end()) {
        return nullptr;
    }
    return iter->second;
}

bool TaskTree_Logic::isTreeMode() const
{
    return m_tree_mode;
}

bool TaskTree_Logic::setTreeMode(bool treeMode)
{
    if (m_tree_mode == treeMode) {
        return false;
    }

    m_tree_mode = treeMode;

    _rebuild_tree();

    return true;
}

SortOrder TaskTree_Logic::getSortOrder() const
{
    return m_sort_order;
}

SortBy TaskTree_Logic::getSortBy() const
{
    return m_sort_by;
}

void TaskTree_Logic::sort(TIP prop, SortOrder order)
{
    _sort(TIPUtils::propToSortBy(prop), order, false);
}

void TaskTree_Logic::_sort_node_vec(vector<Node *> &vec)
{
    std::sort(vec.begin(), vec.end(), _get_sorter());

    vector<Node *>::size_type i, len = vec.size();
    for (i = 0; i < len; ++i) {
        Node * node = vec[i];
        node->index = i;
    }

}

void TaskTree_Logic::_sort_node(Node *node)
{
    if (node) {

        _sort_node_vec(node->children);

        for (Node * n : node->children) {
            _sort_node(n);
        }

    }
}

void TaskTree_Logic::_sort(SortBy sortBy, SortOrder order, bool force)
{
    // 如果不是强制排序， 就先检查和之前的排序依据是否一样， 一样就不重新排序了
    if (!force) {
        if (sortBy == m_sort_by && order == m_sort_order) {
            return;
        }
    }

    m_sort_order = order;
    m_sort_by = sortBy;

    _sort_node_vec(m_roots);

    for (Node * node : m_roots) {
        _sort_node(node);
    }

}

void TaskTree_Logic::_filt(const std::set<pid_t> &all_pid, std::set<pid_t> * filted)
{
    m_filters.filt(all_pid, filted);
}

void TaskTree_Logic::_which(const set<pid_t> &all_pid, set<pid_t> *old_pid, set<pid_t> *new_pid, set<pid_t> *out_of_date) const
{
    for (pid_t pid : all_pid) {
        if (map_contains(m_all_tasks, pid)) {
            old_pid->insert(pid);
        } else {
            new_pid->insert(pid);
        }
    }

    for (const pair<pid_t, Node *> &kv : m_all_tasks) {
        pid_t pid = kv.first;
        if (!set_contains(all_pid, pid)) {
            out_of_date->insert(pid);
        }
    }

}

void TaskTree_Logic::_build_tree()
{
    if (m_tree_mode) {

        for (const pair<pid_t, Node *> &kv : m_all_tasks) {
            pid_t pid  = kv.first;
            pid_t ppid = kv.second->task_info.getPPid();

            if (map_contains(m_all_tasks, ppid)) {

                Node * parent = m_all_tasks[ppid];
                Node * child  = m_all_tasks[pid];

                child->parent = parent;
                parent->children.push_back(child);
            }

        }

        for (const pair<pid_t, Node *> &kv : m_all_tasks) {
            pid_t pid = kv.first;
            Node * node = m_all_tasks[pid];

            if (!node->parent) {
                m_roots.push_back(node);
            }
        }

    } else { // not tree mode

        for (const pair<pid_t, Node *> &kv : m_all_tasks) {
            m_roots.push_back(kv.second);
        }

    }

    _sort(m_sort_by, m_sort_order, true);

}

void TaskTree_Logic::_erase(vector<Node *> &vec, pid_t pid)
{
    int size = int(vec.size());

    for (int i = 0; i < size; ++i) {

        Node * node = vec[i];

        assert(node);

        if (node->pid == pid) {
            vec.erase(vec.begin() + i);
            return;
        }

    }

}

void TaskTree_Logic::_insert(vector<Node *> &vec, Node * node)
{
    vec.push_back(node);
}

void TaskTree_Logic::_delete_child_nodes_for_treemode(Node * node)
{
    assert(node);

    /* 在删除被删除节点的子节点时，因为是从父节点到子节点删除，
    父节点马上要被delete， 所以不需要再修改父节点， 只需要递归地删除所有子节点*/

    for (Node * child : node->children) {
        _delete_child_nodes_for_treemode(child);
    }

    m_all_tasks.erase(node->pid);

    delete node;
}

// 递归地删除某个任务及其子任务， 用于树形模式
void TaskTree_Logic::_delete_task_for_treemode(pid_t pid)
{
    Node * node = _get_node(pid);

    if (node) {

        Node * parent = node->parent;

        if (parent) {
            _erase(parent->children, pid);
        } else {
            _erase(m_roots, pid);
        }

        for (Node * child : node->children) {
            _delete_child_nodes_for_treemode(child);
        }

        m_all_tasks.erase(pid);

        delete node;

    }

}

// 非递归地删除某个任务，保留其子任务， 用于非树形模式
void TaskTree_Logic::_delete_task_not_treemode(pid_t pid)
{
    _erase(m_roots, pid);

    m_all_tasks.erase(pid);

    delete _get_node(pid);
}

void TaskTree_Logic::_delete_out_of_date(const std::set<pid_t> &out_of_date)
{
    for (pid_t pid : out_of_date) {
        m_removed.push_back(Location(pid, getParent(pid), getIndex(pid)));
    }

    if (m_tree_mode) {
        for (pid_t pid : out_of_date) {
            _delete_task_for_treemode(pid);
        }
    } else {
        for (pid_t pid : out_of_date) {
            _delete_task_not_treemode(pid);
        }
    }

}

void TaskTree_Logic::_load_new(const std::set<pid_t> &new_pid)
{
    for (pid_t pid : new_pid) {

        try {
            Node * node = new Node(pid);
            m_all_tasks[pid] = node;

            if (m_tree_mode) {
                TaskInfo &info = node->task_info;
                if (info.hasParent()) {
                    pid_t ppid = info.getPPid();
                    Node * parent = _get_node(ppid);
                    if (parent) {
                        _insert(parent->children, node);
                        node->parent = parent;
                    }
                } else {
                    _insert(m_roots, node);
                }
            } else {
                _insert(m_roots, node);
            }

            m_inserted.push_back(Location(pid));

        } catch (NoSuchFile) {
            // 如果文件已经消失，则捕获这个异常，然后忽略这个进程
            // 文件消失意味着对应的进程已经消失
        }

    }

}



void TaskTree_Logic::_move(Node * node, pid_t old_ppid, pid_t new_ppid)
{
    if (!node) {
        return;
    }

    if (old_ppid == new_ppid) {
        return;
    }

    if (old_ppid < 0 || new_ppid < 0) {
        return;
    }

    if (old_ppid == 0 && new_ppid > 0) {
        _erase(m_roots, node->pid);

        Node * new_parent = _get_node(new_ppid);
        if (new_parent) {
            _insert(new_parent->children, node);
            node->parent = new_parent;
        }

        return;
    }

    if (old_ppid > 0 && new_ppid == 0) {
        Node * old_parent = _get_node(old_ppid);
        if (old_parent) {
            _erase(old_parent->children, node->pid);
        }

        _insert(m_roots, node);
        node->parent = nullptr;

        return;
    }

    if (old_ppid > 0 && new_ppid > 0) {
        Node * old_parent = _get_node(old_ppid);
        if (old_parent) {
            _erase(old_parent->children, node->pid);
        }

        Node * new_parent = _get_node(new_ppid);
        if (new_parent) {
            _insert(new_parent->children, node);
            node->parent = new_parent;
        }

        return;
    }

}

void TaskTree_Logic::_flush_old(const set<pid_t> &old_pid, set<pid_t> * const &out_of_date)
{
    for (pid_t pid : old_pid) {

        try {
            Node * node = _get_node(pid);
            TaskInfo &info = node->task_info;
            info.flush();

            if (m_tree_mode) {
                _move(node, info.getOldPPid(), info.getPPid());
            }

        } catch (NoSuchFile) {
            out_of_date->insert(pid);
        }
    }

}

void TaskTree_Logic::_load_from_sys()
{
    m_inserted.clear();
    m_removed.clear();

    set<pid_t> all_pid;     // 当前所有PID
    set<pid_t> filted_pid;  // 过滤后满足过滤条件的PID
    set<pid_t> old_pid;     // 之前已经发现的PID，这类PID需要进行刷新操作
    set<pid_t> new_pid;     // 之前没有发现的新PID，这类PID要新建结点并插入进程树

    /* 之前发现且已经保存在进程树中，但现在已经消失的PID。
    注意，这里保存的仅仅是之前已经保存在进程树中但后来消失的进程PID，并不是所有消失的PID
    进程在任何时间点都有可能消失， 所以这个对象要使用多次， 请仔细阅读本函数的注释 */
    set<pid_t> out_of_date;

    // 获取当前系统中的所有PID
    ProcFsUtils::getAllPid(&all_pid);

    // 过滤PID，决定哪些保存到进程树
    _filt(all_pid, &filted_pid);

    /* 把过滤后的每个发现的PID归类
    这个函数向out_of_date添加的PID是在上次刷新完成后到这次调用getAllPid之间消失的进程，
    上次刷新过程中，这些PID被保存在进程树中，但在这期间它们消失（结束）了*/
    _which(filted_pid, &old_pid, &new_pid, &out_of_date);

    // 属于新发现的就载入， 如果在这过程中某个找到的进程结束了，就忽略
    _load_new(new_pid);

    /* 刷新之前就保存在进程树中且现在还存在
    在刷新过程中，可能会发现又有一部分进程消失了，这一部分进程消失的阶段是这次调用getAllPid到调用_flush_old之间
    把这些消失的PID号也保存下来 */
    _flush_old(old_pid, &out_of_date);

    // 从进程树中删除已经消失的进程对应的结点，释放内存
    _delete_out_of_date(out_of_date);

    // 每次载入后都强制排序 , 强制体现在第三个参数为true
    _sort(m_sort_by, m_sort_order, true);

    for (Location &location : m_inserted) {
        Node * node = _get_node(location.getPid());
        if (node) {
            location.setPPid(node->task_info.getPPid());
            location.setIndex(node->index);
        }
    }
}

void TaskTree_Logic::_rebuild_tree()
{
    _clear_tree();
    _build_tree();
}

void TaskTree_Logic::addFilter(Filter * filter)
{
    m_filters.addFilter(filter);
}

void TaskTree_Logic::flush()
{
    _load_from_sys();
}

void TaskTree_Logic::_clear_tree()
{
    for (const pair<pid_t, Node *> &kv : m_all_tasks) {
        Node * p = kv.second;
        p->parent = nullptr;
        p->children.clear();
    }

    m_roots.clear();
}

TaskTree_Logic::~TaskTree_Logic()
{
    for (const pair<pid_t, Node *> &kv : m_all_tasks) {
        Node * p = kv.second;
        delete p;
    }

    m_roots.clear();
    m_all_tasks.clear();
}

int TaskTree_Logic::getRootCount() const
{
    return m_roots.size();
}


pid_t TaskTree_Logic::getRootAt(int n) const
{
    if (n >= 0 && n < int(m_roots.size())) {
        return m_roots.at(n)->pid;
    }
    return 0;
}

int TaskTree_Logic::getTaskCount() const
{
    return m_all_tasks.size();
}

bool TaskTree_Logic::contains(pid_t pid) const
{
    return m_all_tasks.find(pid) != m_all_tasks.end();
}

int TaskTree_Logic::getChildCount(pid_t ppid) const
{
    Node * parent = _get_node(ppid);
    if (parent) {
        return parent->children.size();
    }
    return 0;
}

pid_t TaskTree_Logic::getChildAt(pid_t ppid, int n) const
{
    Node * parent = _get_node(ppid);
    if (parent) {
        const vector<Node *> &vec = parent->children;
        if (n >= 0 && n < int(vec.size())) {
            return vec.at(n)->pid;
        }
    }
    return 0;
}

bool TaskTree_Logic::hasParent(pid_t pid) const
{
    Node * p = _get_node(pid);
    if (p) {
        return p->task_info.hasParent();
    }
    return false;
}

pid_t TaskTree_Logic::getParent(pid_t pid) const
{
    Node * p = _get_node(pid);
    if (p) {
        return p->task_info.getPPid();
    }
    return 0;
}

int TaskTree_Logic::getIndex(pid_t pid) const
{
    Node * p = _get_node(pid);
    if (p) {
        return p->index;
    }
    return -1;
}

void TaskTree_Logic::getInserted(std::vector<Location> *vec) const
{
    if (vec) {
        vec->clear();
        for (Location loc : m_inserted) {
            vec->push_back(loc);
        }
    }
}

void TaskTree_Logic::getRemoved(std::vector<Location> *vec) const
{
    if (vec) {
        vec->clear();
        for (Location loc : m_removed) {
            vec->push_back(loc);
        }
    }
}

bool TaskTree_Logic::info(pid_t pid, TaskInfo *info) const
{
    if (info) {

        Node * p = _get_node(pid);
        if (p) {
            (*info) = p->task_info;
            return true;
        }

    }

    return false;
}

typedef bool sorter_t(Node *, Node *);

static bool sorter_by_pid(Node *p1, Node *p2)
{
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_ppid(Node *p1, Node *p2)
{
    pid_t ppid1 = p1->task_info.getPPid();
    pid_t ppid2 = p2->task_info.getPPid();
    if (ppid1 < ppid2) {
        return true;
    }
    if (ppid1 > ppid2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static string to_upper(const string &s)
{
    string res(s);
    string::size_type i, len = res.length();
    for (i = 0; i < len; ++i) {
        char ch = res[i];
        if (islower(ch)) {
            res[i] = toupper(ch);
        }
    }
    return res;
}

static bool sorter_by_name(Node * p1, Node *p2)
{
    const string name1 = to_upper(p1->task_info.getName());
    const string name2 = to_upper(p2->task_info.getName());

    int cmp = name1.compare(name2);
    if (cmp < 0) {
        return true;
    }
    if (cmp > 0) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_username(Node *p1, Node *p2)
{
    uid_t uid1 = p1->task_info.getUid();
    uid_t uid2 = p2->task_info.getUid();

    if (uid1 == uid2) { // UID相等意味着用户名相等，直接使用PID排序
        return p1->task_info.getPid() < p2->task_info.getPid();
    }

    // UID不相等时必须比较用户名，因为UID的大小关系与用户名的大小关系不对应
    // UID不同时UID的比较结果不能代表用户名的比较结果
    const string username1 = p1->task_info.getUserName();
    const string username2 = p2->task_info.getUserName();

    int cmp = username1.compare(username2);
    if (cmp < 0) {
        return true;
    }
    if (cmp > 0) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_state(Node *p1, Node *p2)
{
    TaskState st1 = p1->task_info.getState();
    TaskState st2 = p2->task_info.getState();
    if (st1 < st2) {
        return true;
    }
    if (st1 > st2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_vm_size(Node *p1, Node *p2)
{
    uintptr_t size1 = p1->task_info.getVmSize();
    uintptr_t size2 = p2->task_info.getVmSize();
    if (size1 < size2) {
        return true;
    }
    if (size1 > size2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_vm_resident(Node *p1, Node *p2)
{
    uintptr_t rs1 = p1->task_info.getVmResident();
    uintptr_t rs2 = p2->task_info.getVmResident();
    if (rs1 < rs2) {
        return true;
    }
    if (rs1 > rs2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_vm_shared(Node *p1, Node *p2)
{
    uintptr_t shr1 = p1->task_info.getVmShared();
    uintptr_t shr2 = p2->task_info.getVmShared();
    if (shr1 < shr2) {
        return true;
    }
    if (shr1 > shr2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_vm_private(Node *p1, Node *p2)
{
    uintptr_t prvt1 = p1->task_info.getVmPrivate();
    uintptr_t prvt2 = p2->task_info.getVmPrivate();
    if (prvt1 < prvt2) {
        return true;
    }
    if (prvt1 > prvt2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_cpu_usage(Node *p1, Node *p2)
{
    double usg1 = p1->task_info.getCpuUsage();
    double usg2 = p2->task_info.getCpuUsage();
    if (usg1 < usg2) {
        return true;
    }
    if (usg1 > usg2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_cpu_time(Node *p1, Node *p2)
{
    jiffies_t ct1 = p1->task_info.getCpuTime();
    jiffies_t ct2 = p2->task_info.getCpuTime();
    if (ct1 < ct2) {
        return true;
    }
    if (ct1 > ct2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_start_time(Node *p1, Node *p2)
{
    time_t t1 = p1->task_info.getStartTime();
    time_t t2 = p2->task_info.getStartTime();
    if (t1 < t2) {
        return true;
    }
    if (t1 > t2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_nice(Node *p1, Node *p2)
{
    int nice1 = p1->task_info.getNice();
    int nice2 = p2->task_info.getNice();
    if (nice1 < nice2) {
        return true;
    }
    if (nice1 > nice2) {
        return false;
    }
    return p1->task_info.getPid() < p2->task_info.getPid();
}

static bool sorter_by_cmd(Node *p1, Node *p2)
{
    const string cmd1 = to_upper(p1->task_info.getCmd());
    const string cmd2 = to_upper(p2->task_info.getCmd());
    int cmp = cmd1.compare(cmd2);

    if (cmp < 0) {
        return true;
    }
    if (cmp > 0) {
        return false;
    }

    return p1->task_info.getPid() < p2->task_info.getPid();
}

// 根据排序属性获取一个排序函数指针， 所有排序函数只负责从小到大排序
// 由SorterWrapper负责调整排序方向
static sorter_t * get_sorter(const SortBy &sortBy)
{
    switch (sortBy) {
    case SortBy::PID:
        return sorter_by_pid;
    case SortBy::PPID:
        return sorter_by_ppid;
    case SortBy::NAME:
        return sorter_by_name;
    case SortBy::USERNAME:
        return sorter_by_username;
    case SortBy::STATE:
        return sorter_by_state;
    case SortBy::VM_SIZE:
        return sorter_by_vm_size;
    case SortBy::VM_RESIDENT:
        return sorter_by_vm_resident;
    case SortBy::VM_SHARED:
        return sorter_by_vm_shared;
    case SortBy::VM_PRIVATE:
        return sorter_by_vm_private;
    case SortBy::CPU_USAGE:
        return sorter_by_cpu_usage;
    case SortBy::CPU_TIME:
        return sorter_by_cpu_time;
    case SortBy::START_TIME:
        return sorter_by_start_time;
    case SortBy::NICE:
        return sorter_by_nice;
    case SortBy::CMD:
        return sorter_by_cmd;
    }
    return sorter_by_pid;
}

TaskTree_Logic::SorterWrapper::SorterWrapper(sorter_t *sorter, SortOrder order)
    : sorter(sorter), order(order) {}

bool TaskTree_Logic::SorterWrapper::operator ()(Node *p1, Node *p2)
{
    if (sorter) {
        if (order == SortOrder::ASC) {
            return sorter(p1, p2);
        } else {
            return sorter(p2, p1);
        }
    }
    return true;
}

TaskTree_Logic::SorterWrapper TaskTree_Logic::_get_sorter()
{
    sorter_t *s = get_sorter(m_sort_by);
    if (s) {
        return SorterWrapper(s, m_sort_order);
    } else {
        return SorterWrapper(sorter_by_pid, m_sort_order);
    }
}

/*
使用写时复制技术封装一个TaskTree_Logic，以保证线程安全。
*/
struct TaskTree_Private
{
    TaskTree_Private();
    ~TaskTree_Private();

    TaskTree_Logic * copy() const;             // 复制一个TaskTree_Logic，用于写入
    void replace(TaskTree_Logic * taskTree);   // 写入完成后进行替换，使写入生效

    mutable RWMutex mtx;                       // 用于保证读取和写入的线程安全
    TaskTree_Logic * tree;                     // 被保护的进程树逻辑
};

TaskTree_Private::TaskTree_Private():tree(new TaskTree_Logic) {}

TaskTree_Private::~TaskTree_Private() {delete tree;}

TaskTree_Logic * TaskTree_Private::copy() const
{
    ReadLocker lock(mtx);

    return new TaskTree_Logic(*tree);
}

void TaskTree_Private::replace(TaskTree_Logic *taskTree)
{
    WriteLocker lock(mtx);

    delete tree;

    tree = taskTree;
}

TaskTree::TaskTree()
    : m_data(new TaskTree_Private) {}

TaskTree::~TaskTree()
{
    delete m_data;
}

void TaskTree::addFilter(Filter *filter)
{
    TaskTree_Logic * p = m_data->copy();
    p->addFilter(filter);
    m_data->replace(p);
}

void TaskTree::flush()
{
    TaskTree_Logic * p = m_data->copy();
    p->flush();
    m_data->replace(p);
}

void TaskTree::sort(TIP prop, SortOrder order)
{
    TaskTree_Logic * p = m_data->copy();
    p->sort(prop, order);
    m_data->replace(p);
}

bool TaskTree::setTreeMode(bool treeMode)
{
    TaskTree_Logic * p = m_data->copy();
    bool b = p->setTreeMode(treeMode);
    m_data->replace(p);
    return b;
}

bool TaskTree::isTreeMode() const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->isTreeMode();
}

SortOrder TaskTree::getSortOrder() const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->getSortOrder();
}

SortBy TaskTree::getSortBy() const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->getSortBy();
}

int TaskTree::getRootCount() const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->getRootCount();
}

pid_t TaskTree::getRootAt(int n) const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->getRootAt(n);
}

int TaskTree::getTaskCount() const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->getTaskCount();
}

bool TaskTree::contains(pid_t pid) const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->contains(pid);
}

int TaskTree::getChildCount(pid_t ppid) const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->getChildCount(ppid);
}

pid_t TaskTree::getChildAt(pid_t ppid, int n) const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->getChildAt(ppid, n);
}

bool TaskTree::hasParent(pid_t pid) const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->hasParent(pid);
}

pid_t TaskTree::getParent(pid_t pid) const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->getParent(pid);
}

int TaskTree::getIndex(pid_t pid) const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->getIndex(pid);
}

void TaskTree::getInserted(std::vector<Location> *vec) const
{
    ReadLocker lock(m_data->mtx);
    m_data->tree->getInserted(vec);
}

void TaskTree::getRemoved(std::vector<Location> *vec) const
{
    ReadLocker lock(m_data->mtx);
    m_data->tree->getRemoved(vec);
}

bool TaskTree::info(pid_t pid, TaskInfo *info) const
{
    ReadLocker lock(m_data->mtx);
    return m_data->tree->info(pid, info);
}




